package Offer;

/*
    返回链表中倒数第k个节点
    思路1:
        先遍历一遍链表，计算出结点的个数n ；第二次遍历的时候遍历完前n-k个结点后返回即可
    思路2:
        利用双指针,前后指针距离为k，当后面的指针到达链表的末尾时（指向null），返回前面的指针即可（只需要遍历一次即可）
* */
public class T22_getKthFromEnd {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p1, p2;
        p1 = p2 = head;
        while (k-- > 0) {
            p2 = p2.next;
        }

        while (p2 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}
